package org.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(1/ 2);
    }
}
class Solution {
    int[] tmpNums;// 临时存储归并排序后的元素值
    int[] tmpIndex;// 临时存储归并排序后的元素对应的原始下标
    int[] index;// index[i] 表示当前 nums[i] 元素的原始下标
    ArrayList<Integer> ret;// ret[i] 表示原始数组中第 i 个元素右侧有多少更小的元素
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        tmpNums = new int[n];
        tmpIndex = new int[n];
        index = new int[n];
        ret = new ArrayList<>(n);
        //初始化index和ret
        for (int i = 0; i < n; i++) {
            index[i] = i;
            ret.add(0);
        }

        mergeSort(nums, 0, n - 1);
        return ret;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if(l >= r) return;
        //根据中间元素划分区间
        int mid = (l + r) >> 1;
        //处理左右两个区间
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        //处理一左一右
        int cur1 = l, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= r){
            if(nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
            else{
                // 当前左侧元素大于右侧元素，累加右侧剩余数量
                ret.set(index[cur1], ret.get(index[cur1]) + (r - cur2 + 1));
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        //处理剩余排序
        while(cur1 <= mid){
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }

        while(cur2 <= r){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        for(int k = l; k <= r; k++){
            nums[k] = tmpNums[k - l];
            index[k] = tmpIndex[k - l];//更新存储排序后的元素对应的原始下标
        }
    }
}